package leetbook.link;

import java.util.HashMap;

public class Solution138 {

    class Node{

        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }


    public Node copyRandomList(Node head) {

        //用hash记录原节点到复制节点的映射
        HashMap<Node,Node> hashMap = new HashMap<>();
        //新链表虚拟节点
        Node newHead = new Node(-1);
        Node curTail = newHead;

        while (head!=null){
            Node newNode = new Node(head.val);
            //让新节点的random暂时指向原节点
            newNode.random = head;
            //新旧节点映射
            hashMap.put(head,newNode);
            //把新节点添加到新链表末尾
            curTail.next = newNode;
            curTail = curTail.next;
            head = head.next;
        }

        //再遍历一遍设置random
        Node cur = newHead.next;
        while (cur!=null){
            Node rand = hashMap.get(cur.random.random);
            if(rand!=null) cur.random = rand;
            else cur.random = null;
            cur = cur.next;
        }

        return newHead.next;
    }



}


